public class Demo5 {


    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);

    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int ret = 0;
        int mid = (left + right) / 2;
        //[left,mid]  [mid+1][right]

        //2.求出左右两个区间的逆序对
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        //3.处理一左一右  计算翻转对
        int cur1 = left;
        int cur2 = mid + 1, i = left;

        //降序版本
        while (cur2 <= right) {
            while (cur1 <= mid && nums[cur1]/2.0  < nums[cur2] ) {
                cur1++;
            }
            if (cur1 > mid) {
                break;
            }
            ret += mid - cur1 + 1;
            cur2++;
        }

        //合并
        cur1 = left;
        cur2 = mid+1;
        while (cur1<=mid && cur2<=right){
            tmp[i++] = nums[cur1] >= nums[cur2]?nums[cur2++]:nums[cur1++];
        }
        while (cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while (cur2<=right){
            tmp[i++] = nums[cur2++];
        }


        for(int j = left;j<=right;j++){
            nums[j] = tmp[j];
        }

        return ret;

    }


}
